package interview.questions.从尾到头打印列表;

import java.util.Stack;
import java.util.ArrayList;

/**
 * 问题：
 * <p>
 * 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
 */
public class Solution {
    /**
     * 解决思路：
     * <p>
     * 问题1：是否允许在打印的同时修改链表的结构，这个取决于业务的需求，因此在面试的时候我们要询问清楚面试官的要求。
     * 问题2：通常打印是一个只读操作，我们不希望打印时修改内容。当遍历链表的时候用一个栈存储链表的值，然后依次弹出元素存入ArrayList 中，时间复杂度O(N)
     * 问题3：不在遍历列表的时候顺便将元素前插入的ArrayList的原因是，一边遍历，一边插涉及到ArrayList中数据的移动，时间复杂度是O（N2）
     *
     * @param listNode 链表
     * @return 返回集合ArrayList
     */
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        Stack<Integer> stack = new Stack<Integer>();

        while (listNode != null) {

            stack.push(listNode.val);

            listNode = listNode.next;

        }

        ArrayList<Integer> arrayList = new ArrayList<Integer>();

        while (!stack.empty()) {

            arrayList.add(stack.pop());

        }

        return arrayList;
    }
}
